package 集合.hashCode与equals;

import java.util.AbstractSet;
import java.util.Arrays;
import java.util.Collection;
/*
Java开发规范有一句话：只要重写 equals，就必须重写 hashCode。
关于hashCode和equals的处理：
1.只有重写equqls,就必须重写hashCode
2.因为Set存储的是不重复的对象，依据hashCode和equals进行判断，索引Set存储的对象必须重写这两个方法。
3.如果自定义对象作为Map键，那么必须重写hashCode和equals。
说明：String重写了hashCode和equals方法，所以可以简便的用String作为key来使用，而不必重写hashCode和equals方法


我想很多人都会问为什么，所谓知其然知其所以然，对待知识不单止知道结论还得知道原因。

【hashCoed 的特性】

(1)HashCode的存在主要是用于查找的快捷性，如Hashtable，HashMap等，HashCode经常用于确定对象的存储地址;

(2)如果两个对象相同， equals方法一定返回true，并且这两个对象的HashCode一定相同;

(3)两个对象的HashCode相同，并不一定表示两个对象就相同，即equals()不一定为true，只能够说明这两个对象在一个散列存储结构中。

(4)如果对象的equals方法被重写，那么对象的HashCode也尽量重写。


【hashcode的作用】

Java中的集合有两类，一类是List，再有一类是Set。前者集合内的元素是有序的，元素可以重复;后者元素无序，但元素不可重复。

equals方法可用于保证元素不重复，但如果每增加一个元素就检查一次，若集合中现在已经有1000个元素，那么第1001个元素加入集合时，就要调用1000次equals方法。这显然会大大降
低效率。?于是，Java采用了哈希表的原理。

哈希算法也称为散列算法，是将数据依特定算法直接指定到一个地址上。

这样一来，当集合要添加新的元素时，先调用这个元素的HashCode方法，就一下子能定位到它应该放置的物理位置上。

1)如果这个位置上没有元素，它就可以直接存储在这个位置上，不用再进行任何比较了。

2)如果这个位置上已经有元素了，就调用它的equals方法与新元素进行比较，相同的话就不存了。

3)不相同的话，也就是发生了Hash key相同导致冲突的情况，那么就在这个Hash key的地方产生一个链表，将所有产生相同HashCode的对象放到这个单链表上去，串在一起(很少出现)。


Java 基础之 hashcode 剖析

1. 前言
散列是计算机科学的一个基本概念。在 Java 中，高效的散列算法支持一些最流行的集合，例如 HashMap 和 HashSet,在本文中，我们将重点介绍 hashCode() 的工作原理、它如
何在集合中使用以及如何正确实现它。

【hashcode 规则】

	-在 equals 方法没被修改的前提下，多次调用同一对象的 hashcode 方法返回的值必须是相同的整数；
	-如果两个对象互相 equals，那么这两个对象的 hashcode 值必须相等；
	-为不同对象生成不同的 hashcode 可以提升哈希表的性能；

【目标】

	1)为什么要 重写 hashcode 和 equals 方法
	2)为什么两个对象相等，Set 、Map 还是打印两个对象引用？
	3)只重写 equals 方法和只重写 hashcode 方法会出现什么情况？

2. hashcode 原理
2.1 Java equals()和 hashCode()的关系

【hashcode 的理解】

	1)hashCode 的存在主要是用于查找的快捷性，如 Hashtable，HashMap 等，hashCode 是用来在散列存储结构中确定对象的存储地址的；
	2)如果两个对象相同，就是适用于 equals(java.lang.Object) 方法，那么这两个对象的 hashCode 一定要相同；
	3)如果对象的 equals 方法被重写，那么对象的 hashCode 也尽量重写，并且产生 hashCode 使用的对象，一定要和 equals 方法中使用的一致，否则就会违反上面提到
	  的第 2 点；
	4)两个对象的 hashCode 相同，并不一定表示两个对象就相同，也就是不一定适用于 equals(java.lang.Object) 方法，只能够说明这两个对象在散列存储结构中，
	  如 Hashtable，他们 “存放在同一个篮子里” 。

再归纳一下就是 hashCode 是用于查找使用的，而 equals 是用于比较两个对象的是否相等的。以下这段话是从别人帖子回复拷贝过来的，说的很形象：

(1) hashcode 是用来查找的，如果你学过数据结构就应该知道，在查找和排序说过：假如内存中有这样的位置 [0 1 2 3 4 5 6 7] 而我有个类，这个类有个字段叫 ID,我要把这
个类存放在以上 8 个位置之一，如果不用 hashcode 而任意存放，那么当查找时就需要到这八个位置里挨个去找，或者用类似二分法的算法。 但如果用 hashcode 那就会使效率提
高很多。

我们这个类中有个字段叫 ID,那么我们就定义我们的 hashcode 为 ID％8，然后把我们的类存放在取得得余 数那个位置。比如我们的 ID 为 9，9 除 8 的余数为 1，那么我们就
把该类存在 1 这个位置，如果 ID 是 13，求得 的余数是 5，那么我们就把该类放在 5 这个位置。这样，以后在查找该类时就可以通过 ID 和 8 求余数直接找到存放的位置了。

(2) 但是如果两个类有相同的 hashcode 该怎么办呢（假设上面的 ID 不是唯一的），假如 9%8=1，17%8=1，那么这是不是合法的呢？回答是：可以这样。

那么如何判断呢？在这个时候就需要定义 equals 了。也就是说，我们先通过 hashcode 来判断两个类是否存放在一个桶里面，但是这个桶里面可以有很多类，那么我们就需要
通过 equals 来在这个桶里找到我们要的类。

那么。重写了 equals()，为什么还要重写 hashCode()呢？

想想，你要在一个桶里找东西，你必须先要找到这个桶啊，你不通过重写 hashcode()来找到桶，光重写 equals()有什么用啊

2.2 Object 的 hashcode 分析

*/
/*
import java.util.HashSet;
import java.util.Set;

//public class DemoHashCode {
public class 使用hashCode {

    private int id;

    public void setId(Integer id) {
        this.id = id;
    }

    public Integer getId() {
        return id;
    }

    @Override
    public int hashCode() {
        return id % 10;
    }

    public static void main(String[] args) {
   	 使用hashCode a = new 使用hashCode();
   	 使用hashCode b = new 使用hashCode();
        a.setId(1);
        b.setId(1);
        Set<使用hashCode> set = new HashSet<>();
        set.add(a);
        set.add(b);
        System.out.println(a.hashCode() == b.hashCode());
        System.out.println(a.equals(b));
        System.out.println(set);

        //运行结果：
        //true
        //false
        //[集合.使用hashCode@1, 集合.使用hashCode@1]
    }
}
*/
/*
以上这个示例，我们只重写了 hashcode() 方法，从上面的结果可以看出，虽然两个对象的 hashcode 相等，但实际上两个对象并不相等。

我们没有重写 equals()方法，那么就会调用 Object 默认的 equals()方法，是比较两个对象的引用是不是相同，实际上两个对象的引用肯定是不等的，这里我们将生成的对象放到
了 HashSet 中，而 HashSet 中只能够存放唯一的对象，也就是相同的（适用于 equals 方法）的对象只会存放一个，但是这里实际上是两个对象 a,b 都被放到了 HashSet 中，
这样 HashSet 就失去了他本身的意义了。 此时我们把 equals 方法给加上：
*/
/*
import java.util.HashSet;
import java.util.Set;


public class 使用hashCode {

    private int id;

    public void setId(Integer id) {
        this.id = id;
    }

    public Integer getId() {
        return id;
    }

    @Override
    public boolean equals(Object o) {
   	 System.out.println(getClass());
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        使用hashCode that = (使用hashCode) o;
        return id == that.id;
    }

    @Override
	public int hashCode() {
    	System.out.println("hashCode() called - Computed hash: " + id%10);
      return id % 10;
   }

    public static void main(String[] args) {
   	 使用hashCode a = new 使用hashCode();
   	 使用hashCode b = new 使用hashCode();
        a.setId(1);
        b.setId(1);
        Set<使用hashCode> set = new HashSet<>();
        set.add(a);
        set.add(b);
        System.out.println(a.hashCode() == b.hashCode());
        System.out.println(a.equals(b));
        System.out.println(set);
        System.out.println("asdfasdasdasdasdasd");
       
        //运行结果：
        //true
        //true
        //[集合.使用hashCode@1]
    }
}
*/
/*
从结果我们可以看出，现在两个对象就完全相等了，HashSet 中也只存放了一份对象。

2.3 hashmap 的 hashcode 分析
hashMap 组成结构：hashMap 是由数组和链表组成；

	-hashMap 的存储：一个对象存储到 hashMap 中的位置是由其 key 的 hashcode 值决定的;

	-查 hashMap 查找 key: 找 key 的时候 hashMap 会先根据 key 值的 hashcode 经过取余算法定位其所在数组的位置，再根据 key 的 equals 方法匹配相
	同 key 值获取对应相应的对象；

(1)HashMap 存储 key

	-存值规则： 把 Key 的 hashCode 与 HashMap 的容量 取余得出该 Key 存储在数组所在位置的下标 （源码定位 Key 存储在数组的哪个位置是
	以 hashCode & (HashMap 容量-1)算法得出）

为了演示方便定义一个容量大小为 3 的 hashMap（其默认为 16）

​HashMap map=newHashMap(3);
 
map.put("a",1); 得到key 为“a” 的hashcode 值为97然后根据 该值和hashMap 容量取余97%3得到存储位到数组下标为1;
 
map.put("b",2); 得到key 为“b” 的hashcode 值为98,98%3到存储位到数组下标为2;
 
map.put("c",3); 得到key 为“c” 的hashcode 值为99，99%3到存储位到数组下标为0;
 
map.put("d",4); 得到key 为“d” 的hashcode 值为100，100%3到存储位到数组下标为1;
 
map.put("e",5); 得到key 为“e” 的hashcode 值为101，101%3到存储位到数组下标为2;
 
map.put("f",6); 得到key 为“f” 的hashcode 值为102，102%3到存储位到数组下标为0;

  0 -- c --> f
  1 -- a --> d
  2 -- b --> e

(2) hashmap 查找 key

	-得到 key 在数组中的位置：根据上图，当我们获取 key 为“a”的对象时，那么我们首先获得 key 的 hashcode97%3 得到存储位到数组下标为 1;

	-匹配得到对应 key 值对象：得到数组下表为 1 的数据“a”和“d”对象， 然后再根据key.equals()来匹配获取对应 key 的数据对象；

hashcode 对于 HashMap:如果没有 hashcode 就意味着 HashMap 存储的时候是没有规律可寻的，那么每当我们 map.get()方法的时候，就要把 map 里面的对象一一拿出来
进行 equals 匹配，这样效率是不是会超级慢；

3. hash 冲突
哈希表的内在行为也带来了相应的问题：即使使用有效的哈希算法，两个或多个对象可能具有相同的哈希码，即使两个对象不相等。因此，即使它们具有不同的散列值，它们的散列码也会指向
同一个桶。 这种情况通常被称为散列冲突。

解决 hash 冲突的方法，详细分析可以点此处查看：

	-链表法
	-开放寻址法

Java 中的 hashMap 是使用链表法解决 hash 冲突的

当两个或多个对象指向同一个存储桶时，它们只是存储在一个链表中。在这种情况下，哈希表是一个链表数组，每个具有相同哈希值的对象都附加到链表中的桶索引处。

在最坏的情况下，几个桶会绑定一个链表，而对链表中对象的检索将是线性执行的。

处理哈希冲突 简言之，为什么高效地实现 hashCode()如此重要？

Java8 也为 HashMap 的实现进行了增强，如果桶大小超过 8，节点入超过 64，则会转换为红黑树，而不是使用链表，这样当链表太长接近线性查找（复杂度为 O(n)）时 用红黑
树 O(logN) 代替。

3.1 hashmap 和 hashcode 的联系

User 类中我们重写 hashcode 方法
*/
import java.util.HashMap;
import java.util.Map;
import java.util.Set;
import java.util.HashMap.Node;
import java.util.HashMap.TreeNode;

import jdk.internal.vm.annotation.IntrinsicCandidate;
//@Data
class Usera {
    private long userId;
    private String userName;
    private String email;

    @Override
    public int hashCode() {
        int hash = 7;
        hash = 31 * hash + (int) userId;
        hash = 31 * hash + (userName == null ? 0 : userName.hashCode());
        hash = 31 * hash + (email == null ? 0 : email.hashCode());
        System.out.println("hashCode() called - Computed hash: " + hash);
        return hash;
    }

    public Usera(Long userId, String userName, String email) {
        this.userId = userId;
        this.userName = userName;
        this.email = email;
    }
}

public class 使用hashCode {
    public static void main(String[] args) {
        Map<Usera, Usera> users = new HashMap<>();
        Usera user1 = new Usera(1L, "John", "john@domain.com");
        Usera user2 = new Usera(2L, "Jennifer", "jennifer@domain.com");
        Usera user3 = new Usera(3L, "Mary", "mary@domain.com");
        users.put(user1, user1);
        users.put(user2, user2);
        users.put(user3, user3);

        if (users.containsKey(user1)) {
            System.out.print("User found in the collection");
        }
    }
}

/*
在这里，重要的是要注意，每次将对象存储在哈希映射中并使用 containsKey() 方法检查时，都会调用 hashCode() 并将计算出的哈希码打印到控制台：
hashCode() called - Computed hash: 1255477819
hashCode() called - Computed hash: -282948472
hashCode() called - Computed hash: -1540702691
hashCode() called - Computed hash: 1255477819
User found in the collection
4. 总结
我们没有重写父类（Object）的 hashcode 方法,Object 的 hashcode 方法会根据两个对象的地址生成对相应的 hashcode；

person1 和 person2 是分别 new 出来的，那么他们的地址肯定是不一样的，自然 hashcode 值也会不一样。

Set 区别对象是不是唯一的标准是，首先判断两个对象 hashcode 是不是一样，再判定两个对象是否 equals;

Map 是先根据 Key 值的 hashcode 分配和获取对象保存数组下标的，然后再根据 equals 区分唯一值


一、为什么要有Hash算法
Java中的集合有两类，一类是List，一类是Set。List内的元素是有序的，元素可以重复。Set元素无序，但元素不可重复。要想保证元素不重复，两个元素是否重复应该依据什么来判断呢？用Object.equals方法。但若每增加一个元素就检查一次，那么当元素很多时，后添加到集合中的元素比较的次数就非常多了。也就是说若集合中已有1000个元素，那么第1001个元素加入集合时，它就要调用1000次equals方法。这显然会大大降低效率。于是Java采用了哈希表的原理。哈希(Hash)是个人名，由于他提出哈希算法的概念就以他的名字命名了。

二、Hash算法原理

HashCode的官方文档定义：

hashCode 的常规协定是：

1.在 Java 应用程序执行期间，只要对象的 equals 比较操作所用的信息没有被修改，那么在同一对象上多次调用 hashCode 方法时，必须一致地返回相同的整数，。从某一应用程序的一次执行到同一应用程序的另一次执行，该整数无需保持一致。   
2.如果根据 equals(Object) 方法，两个对象是相等的，那么在两个对象中的每个对象上调用 hashCode 方法都必须生成相同的整数结果。   
3.如果根据 equals(java.lang.Object) 方法，两个对象不相等，那么在两个对象中的任一对象上调用 hashCode 方法不一定要产生不同的整数结果。但是，程序员应该知道，为不相等的对象生成不同整数结果可以提高哈希表的性能。 
复制
1.hashcode是用来查找的，如果你学过数据结构就应该知道，在查找和排序这一章有
例如内存中有这样的位置
0  1  2  3  4  5  6  7  
而我有个类，这个类有个字段叫ID,我要把这个类存放在以上8个位置之一，如果不用hashcode而任意存放，那么当查找时就需要到这八个位置里挨个去找，或者用二分法一类的算法。
但如果用hashcode那就会使效率提高很多。
我们这个类中有个字段叫ID,那么我们就定义我们的hashcode为ID％8，然后把我们的类存放在取得得余数那个位置。比如我们的ID为9，9除8的余数为1，那么我们就把该类存在1这个位置，如果ID是13，求得的余数是5，那么我们就把该类放在5这个位置。这样，以后在查找该类时就可以通过ID除 8求余数直接找到存放的位置了。

2.但是如果两个类有相同的hashcode怎么办那（我们假设上面的类的ID不是唯一的），例如9除以8和17除以8的余数都是1，那么这是不是合法的，回答是：可以这样。那么如何判断呢？在这个时候就需要定义 equals了。
也就是说，我们先通过 hashcode来判断两个类是否存放某个桶里，但这个桶里可能有很多类，那么我们就需要再通过 equals 来在这个桶里找到我们要的类。
那么。重写了equals()，为什么还要重写hashCode()呢？
想想，你要在一个桶里找东西，你必须先要找到这个桶啊，你不通过重写hashcode()来找到
复制
当Set接收一个元素时根据该对象的信息算出hashCode，看它属于哪一个区间，在这个区间里调用equeals方法。


确实提高了效率。但一个面临问题：若两个对象equals相等，但不在一个区间，根本没有机会进行比较，会被认为是不同的对象。所以Java对于eqauls方法和hashCode方法是这样规定的：

1 如果两个对象相同，那么它们的hashCode值一定要相同。也告诉我们重写equals方法，一定要重写hashCode方法。

2 如果两个对象的hashCode相同，它们并不一定相同，这里的对象相同指的是用eqauls方法比较。

三、hashCode方法的分析

哈希表这个数据结构想必大多数人都不陌生，而且在很多地方都会利用到hash表来提高查找效率。在Java的Object类中有一个方法:

public native int hashCode();

　　为何Object类需要这样一个方法？它有什么作用呢？今天我们就来具体探讨一下hashCode方法。根据这个方法的声明可知，该方法返回一个int类型的数值，并且是本地方法，因此在Object类中并没有给出具体的实现。

　　对于包含容器类型的程序设计语言来说，基本上都会涉及到hashCode。在Java中也一样，hashCode方法的主要作用是为了配合基于散列的集合一起正常运行，这样的散列集合包括HashSet、HashMap以及HashTable。

　　为什么这么说呢？考虑一种情况，当向集合中插入对象时，如何判别在集合中是否已经存在该对象了？（注意：集合中不允许重复的元素存在）

　　也许大多数人都会想到调用equals方法来逐个进行比较，这个方法确实可行。但是如果集合中已经存在一万条数据或者更多的数据，如果采用equals方法去逐一比较，效率必然是一个问题。此时hashCode方法的作用就体现出来了，当集合要添加新的对象时，先调用这个对象的hashCode方法，得到对应的hashcode值，实际上在HashMap的具体实现中会用一个table保存已经存进去的对象的hashcode值，如果table中没有该hashcode值，它就可以直接存进去，不用再进行任何比较了；如果存在该hashcode值，  就调用它的equals方法与新元素进行比较，相同的话就不存了，不相同就散列其它的地址，所以这里存在一个冲突解决的问题，这样一来实际调用equals方法的次数就大大降低了，说通俗一点：Java中的hashCode方法就是根据一定的规则将与对象相关的信息（比如对象的存储地址，对象的字段等）映射成一个数值，这个数值称作为散列值。下面这段代码是java.util.HashMap的中put方法的具体实现：



public V put(K key, V value) {
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key.hashCode());
        int i = indexFor(hash, table.length);
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
 
        modCount++;
        addEntry(hash, key, value, i);
        return null;
    }

 put方法是用来向HashMap中添加新的元素，从put方法的具体实现可知，会先调用hashCode方法得到该元素的hashCode值，然后查看table中是否存在该hashCode值，如果存在则调用equals方法重新确定是否存在该元素，如果存在，则更新value值，否则将新的元素添加到HashMap中。从这里可以看出，hashCode方法的存在是为了减少equals方法的调用次数，从而提高程序效率。

因此有人会说，可以直接根据hashcode值判断两个对象是否相等吗？肯定是不可以的，因为不同的对象可能会生成相同的hashcode值。虽然不能根据hashcode值判断两个对象是否相等，但是可以直接根据hashcode值判断两个对象不等，如果两个对象的hashcode值不等，则必定是两个不同的对象。如果要判断两个对象是否真正相等，必须通过equals方法。

　　也就是说对于两个对象，如果调用equals方法得到的结果为true，则两个对象的hashcode值必定相等；

　　如果equals方法得到的结果为false，则两个对象的hashcode值不一定不同；

　　如果两个对象的hashcode值不等，则equals方法得到的结果必定为false；

如果两个对象的hashcode值相等，则equals方法得到的结果未知。

四、覆写equals时总要覆盖HashCode

如果不覆盖会怎么样，这样就违反了第二条规定，相等的对象必须具有相等的散列码

如果不写，即使是相等的对象，返回的就是两个不同的散列码

public class Person {

private String  name;

private Integer  age;

public Person(Stringname, Integerage) {

super();

this.name =name;

this.age =age;

}

@Override

public boolean equals(Objectobj) {

if (this ==obj)

return true;

if (obj ==null)

return false;

if (getClass() !=  obj.getClass())

return false;

Person other = (Person)  obj;

if (age ==null) {

if (other.age !=null)

return false;

} else if (!age.equals(other.age))

return false;

if (name ==null) {

if (other.name !=null)

return false;

} else if (!name.equals(other.name))

return false;

return true;

}

public static void main(String[]args) {

Person p=new Person("汤高",20);

Person p1=new Person("汤高",20);

Map<Person,String> m=new HashMap<Person,String>();

m.put(p,"student");

System.out.println(p1.hashCode()==p.hashCode());

System.out.println("我要得到刚刚的对象");

m.put(p1,"student");

System.out.println(m.get(p1));

System.out.println(m.size());

}

}

结果：

false

我要得到刚刚的对象

Null

2

虽然通过重写equals方法使得逻辑上姓名和年龄相同的两个对象被判定为相等的对象（跟String类类似），但是要知道默认情况下，hashCode方法是将对象的存储地址进行映射。那么上述代码的输出结果为“null”就不足为奇了。原因很简单，p指向的对象和P1指向的对象是两个对象，它们的存储地址肯定不同。下面是HashMap的get方法的具体实现：

public V get(Object key) {

 if (key == null)

 return getForNullKey();

 int hash = hash(key.hashCode());

 for (Entry<K,V> e = table[indexFor(hash, table.length)];

             e != null;

             e = e.next) {

            Object k;

 if (e.hash == hash && ((k = e.key) == key || key.equals(k)))

 return e.value;

        }

 return null;

    }

所以在hashmap进行get操作时，因为得到的hashcdoe值不同（注意，上述代码也许在某些情况下会得到相同的hashcode值，不过这种概率比较小，因为虽然两个对象的存储地址不同也有可能得到相同的hashcode值），所以导致直接返回null。

看看重写了hashcode方法的结果

加入hashcode方法

@Override

public int hashCode() {

final int prime = 31;

int result = 1;

result =  prime * result + ((age ==null) ? 0 :age.hashCode());

result =  prime * result + ((name ==null) ? 0 :name.hashCode());

return result;

}

结果：

true

我要得到刚刚的对象

Student

1

实际上，由 Object 类定义的 hashCode 方法确实会针对不同的对象返回不同的整数。（这一般是通过将该对象的内部地址转换成一个整数来实现的，） 

当equals方法被重写时，通常有必要重写 hashCode 方法，以维护 hashCode 方法的常规协定，该协定声明相等对象必须具有相等的哈希码。




Java 重写 hashCode 方法总结
public int hashCode()
hashCode 约定：

	-若 x.equals(y) 返回 true ，则 x.hashCode()==y.hashCode() ，其逆命题不一定成立。
	-尽量使 hashCode 方法返回的散列码总体上呈均匀分布，可以提高哈希表的性能。
	-程序运行时，若对象的 equals 方法中使用的字段没有改变，则在程序结束前，多次调用 hashCode 方法都应返回相同的散列码；程序结束后再执行时则没有此要求。


以下两点为个人看法：

	-hashCode 方法与 equals 方法应使用相同的字段，这样可以实现第一条约定。
	-若 hashCode 方法使用的字段总体上呈某种概率分布，则可利用概率论的知识构造出总体呈均匀分布的散列码。
工具：

· ^                           //异或运算符
·<< or >> or >>>              //左移运算符或右移运算符   >>>无符号右移
·13、17、31、1231、1237       //重写 hashCode 方法时常用的素数
·hashCode()                      //每一个类都自带的方法
·Objects.hashCode(Object o)      //return o != null ? o.hashCode() : 0;
·Objects.hash(Object... values) //return Arrays.hashCode(values);  
·Arrays.hashCode(Object[] a) 及其重载方法
·包装器的静态方法 hashCode
将以上工具单独使用或组合使用即可重写 hashCode 方法。

示例：

/**
* 异或运算符与无符号右移运算符组合计算的示例
* Long.hashCode(long value)
*/
public static int hashCode(long value) {
    return (int)(value ^ value >>> 32);
}


/**
* 若有bool型字段参与散列码运算可参考以下表达式
* Boolean.hashCode(boolean value)
*/
public static int hashCode(boolean value) {
    return value ? 1231 : 1237;
}
/**
* 若有double型与float型字段参与散列码运算可使用一下方法
 * doubleToLongBits(value) or floatToIntBits(value)
*/
public int hashCode() {
    return (int)Double.doubleToLongBits(this.field)
            + this.intfield * 13;
}


/**
* 最简单的hasnCode方法重写，一般出现在数值型类中
* Integer类的static方法
*/
public static int hashCode(int value) {
    return value;
}


/**
* 集合类重写hashCode方法的典型示例 1
* Arrays.hashCode(Object[] a)的源码
*/
public static int hashCode(Object[] a) {
    if (a == null) {
      return 0;
    } else {
        int result = 1;
        Object[] var2 = a;
        int var3 = a.length;
        for(int var4 = 0; var4 < var3; ++var4) {
            Object element = var2[var4];
            //(element == null ? 0 : element.hashCode())
            // 其实是Objects.hashCode(Object o) 方法的内联形式
            result = 31 * result + (element == null ? 0 : element.hashCode());
        }
        return result;
    }
}
/**
* 集合类重写hashCode方法的典型示例 2
* LinkedList<E>的hashCode方法
*/
public int hashCode() {
    int hashCode = 1;
    Object e;
    //for循环太长了，有3行
    for(Iterator i = this.iterator();
        i.hasNext(); 
        hashCode = 31 * hashCode + (e == null ? 0 : e.hashCode())) {
        e = i.next();
    }
    return hashCode;
}


/**
* 比较省事的重写 hashCode 方法就是用别人的轮子
* Objects.hash 方法借助Arrays.hashCode 方法帮助我们组合散列码
*/
public int hashCode() {
    return Objects.hashCode(this.field, this.Id, this.name)
}
/**
*/
public int hashCode() {
    return Arrays.hashCode(this.intArrayfield);
}


/**
* 如果基类已经重写 hashCode 方法也可以直接用
*/
public int hashCode(){
    return Objects.hash(super.hashCode(), this.bonus);
}


/**
* final修饰的类可以设置一个hash字段专门用来保存散列码
* 如String类的hashCode 方法多次调用但仅计算一次散列码
*/
public int hashCode() {
    int h = this.hash;
    if (h == 0 && this.value.length > 0) {
        this.hash = h = 
             this.isLatin1() ? 
                  StringLatin1.hashCode(this.value) 
                  : StringUTF16.hashCode(this.value);
    }
    return h;
}



【Java hashCode() 指南】

1. 概述

哈希是计算机科学的一个基本概念。

在 Java 中，高效的哈希算法支持一些最流行的集合，例如 HashMap（查看这篇深入的 文章）和 HashSet。

在本教程中，我们将重点介绍 hashCode() 的工作原理、它如何在集合中处理以及如何正确实现它。

2.在数据结构中使用hashCode()
在某些情况下，最简单的集合操作可能效率低下。

举例来说，这会触发线性搜索，这对于大型列表效率非常低：

Java hashCode() 指南
Java 提供了许多数据结构来专门处理这个问题。 例如，几个 Map 接口实现是 hash tables（哈希表）。

使用哈希表时，这些集合使用 hashCode() 方法计算给定键的哈希值。然后他们在内部使用这个值来存储数据，以便访问操作更加高效。

3.了解hashCode()的工作原理
简而言之，hashCode() 返回一个由散列算法生成的整数值。

相等的对象（根据它们的 equals()）必须返回相同的哈希码。不同的对象不需要返回不同的哈希码。

hashCode() 的通用契约声明：

在 Java 应用程序执行期间，只要在同一对象上多次调用它，hashCode() 必须始终返回相同的值，前提是对象上的 equals 比较中使用的信息没有被修改。这个值不需要从应用
程序的一次执行到同一应用程序的另一次执行保持一致。

如果根据 equals(Object) 方法两个对象相等，则对这两个对象中的每一个调用 hashCode() 方法必须产生相同的值。

如果根据 equals(java.lang.Object) 方法两个对象不相等，则对这两个对象中的每一个调用 hashCode 方法不需要产生不同的整数结果。但是，开发人员应该意识到，为不
相等的对象生成不同的整数结果可以提高哈希表的性能。

“在合理可行的情况下，类 Object 定义的 hashCode() 方法确实为不同的对象返回不同的整数。（这通常通过将对象的内部地址转换为整数来实现，但 JavaTM 编程语言不需要
这种实现技术。）”

4.一个简单的hashCode()实现
一个完全符合上述约定的简单 hashCode() 实现实际上非常简单。

为了演示这一点，我们将定义一个示例 User 类来覆盖该方法的默认实现：

public class User {
	private long id;    
	private String name;    
	private String email;    // standard getters/setters/constructors    
	@Override    
	public int hashCode() {        
		return 1;    
	}    
	@Override    
	public boolean equals(Object o) {
		if (this == o)            
			return true;        
		if (o == null)            
			return false;        
		if (this.getClass() != o.getClass())            
			return false;        
		User user = (User) o;        
		return id == user.id && (name.equals(user.name) && email.equals(user.email));    
	}    // getters and setters here}
}
User 类为完全遵守各自合同的 equals() 和 hashCode() 提供自定义实现。更重要的是，让 hashCode() 返回任何固定值并没有什么不合法的。

但是，这种实现将哈希表的功能降级到基本上为零，因为每个对象都将存储在同一个单个存储桶中。

在这种情况下，哈希表查找是线性执行的，并没有给我们带来任何真正的优势。我们将在第 7 节详细讨论。

5.改进 hashCode() 实现
让我们通过包含 User 类的所有字段来改进当前的 hashCode() 实现，以便它可以为不相等的对象产生不同的结果：

@Override
public int hashCode() {
	return (int) id * name.hashCode() * email.hashCode();
	}
这个基本的散列算法绝对比前一个好得多。这是因为它仅通过将 name 和 email 字段的哈希码与 id 相乘来计算对象的哈希码。

一般来说，我们可以说这是一个合理的 hashCode() 实现，只要我们保持 equals() 实现与其一致。

6.标准 hashCode() 实现
我们用来计算哈希码的哈希算法越好，哈希表的性能就越好。

让我们看看一个“标准”实现，它使用两个素数为计算出的哈希码添加更多的唯一性：

@Overridepublic 
int hashCode() {
	int hash = 7;    
	hash = 31 * hash + (int) id;    
	hash = 31 * hash + (name == null ? 0 : name.hashCode());    
	hash = 31 * hash + (email == null ? 0 : email.hashCode());    
	return hash;
	}
虽然我们需要了解 hashCode() 和 equals() 方法所扮演的角色，但我们不必每次都从头开始实现它们。这是因为大多数 IDE 可以生成自定义 hashCode() 和 equals() 实
现。从 Java 7 开始，我们有一个 Objects.hash() 实用方法来进行舒适的散列：

Objects.hash(name, email)
IntelliJ IDEA 生成以下实现：

@Overridepublic 
int hashCode() {
	int result = (int) (id ^ (id >>> 32));    
	result = 31 * result + name.hashCode();    
	result = 31 * result + email.hashCode();   
	return result;
	}
Eclipse 产生了这个：

@Override
public int hashCode() {
	final int prime = 31;    
	int result = 1;    
	result = prime * result + ((email == null) ? 0 : email.hashCode());    
	result = prime * result + (int) (id ^ (id >>> 32));    
	result = prime * result + ((name == null) ? 0 : name.hashCode());    
	return result;
	}
除了上述基于 IDE 的 hashCode() 实现之外，还可以自动生成高效的实现，例如使用 Lombok.。

在这种情况下，我们需要在 pom.xml 中添加 lombok-maven 依赖：

<dependency>  
	<groupId>org.projectlombok</groupId>  
	<artifactId>lombok-maven</artifactId>  
	<version>1.16.18.0</version>  
	<type>pom</type>
</dependency>
现在用@EqualsAndHashCode 注解 User 类就足够了：

@EqualsAndHashCode
public class User {    
	// fields and methods here
}
同样，如果我们希望 Apache Commons Lang 的 HashCodeBuilder 类为我们生成 hashCode() 实现，我们在 pom 文件中包含 commons-lang Maven 依赖项：

public class User {
	public int hashCode() {
		return new HashCodeBuilder(17, 37).
				append(id).
				append(name).
				append(email).
				toHashCode();
		}
	}
一般来说，在实现 hashCode() 时没有通用的方法。我们强烈推荐阅读 Joshua Bloch 的 Effective Java.。它提供了实现高效散列算法的详尽指南列表。

请注意，所有这些实现都以某种形式使用了数字 31。这是因为 31 有一个很好的属性。它的乘法可以用按位移位代替，这比标准乘法要快：

31 * i == (i << 5) - i
7.处理哈希冲突
哈希表的内在行为带来了这些数据结构的一个相关方面：即使使用有效的哈希算法，两个或多个对象可能具有相同的哈希码，即使它们不相等。因此，即使它们具有不同的散列表键，
它们的散列码也会指向同一个桶。

这种情况通常被称为哈希冲突，有多种处理方法，每种方法都有其优点和缺点。Java 的 HashMap 使用单独的链接方法来处理冲突：

.“当两个或多个对象指向同一个存储桶时，它们只是存储在一个链表中。在这种情况下，哈希表是一个链表数组，每个具有相同哈希值的对象都附加到链表中的桶索引处。

在最坏的情况下，几个桶会绑定一个链表，而对链表中对象的检索将是线性执行的。”

哈希冲突方法简单说明了高效实现 hashCode() 的重要性。

Java 8 为 HashMap 实现带来了有趣的增强。如果桶大小超过特定阈值，则树图替换链表。这允许实现 O(logn) 查找而不是悲观 O(n)。

8.创建一个简单的应用程序
现在我们将测试标准 hashCode() 实现的功能。

让我们创建一个简单的 Java 应用程序，将一些 User 对象添加到 HashMap 并使用 SLF4J 在每次调用该方法时将消息记录到控制台。

这是示例应用程序的入口点：

public class Application {
	public static void main(String[] args) { 
		Map<User, User> users = new HashMap<>();
		User user1 = new User(1L, "John", "john@domain.com");
		User user2 = new User(2L, "Jennifer", "jennifer@domain.com");
		User user3 = new User(3L, "Mary", "mary@domain.com");
		users.put(user1, user1);
		users.put(user2, user2);
		users.put(user3, user3);
		if (users.containsKey(user1)) {
			System.out.print("User found in the collection");
			}
		}
	}
这是 hashCode() 实现：

public class User {
	// ...    
	public int hashCode() {
		int hash = 7;
		hash = 31 * hash + (int) id;
		hash = 31 * hash + (name == null ? 0 : name.hashCode());
		hash = 31 * hash + (email == null ? 0 : email.hashCode());
		logger.info("hashCode() called - Computed hash: " + hash);
		return hash;
		}
	}
}
这里需要注意的是，每次在哈希映射中存储对象并使用 containsKey() 方法检查时，都会调用 hashCode() 并将计算出的哈希码打印到控制台：

[main] INFO com.baeldung.entities.User - hashCode() called - Computed hash: 1255477819
[main] INFO com.baeldung.entities.User - hashCode() called - Computed hash: -282948472
[main] INFO com.baeldung.entities.User - hashCode() called - Computed hash: -1540702691
[main] INFO com.baeldung.entities.User - hashCode() called - Computed hash: 1255477819User found in the collection
9.结论
很明显，生成高效的 hashCode() 实现通常需要混合一些数学概念（即素数和任意数）、逻辑和基本数学运算。

无论如何，我们可以有效地实现 hashCode() ，而无需使用这些技术。我们只需要确保散列算法为不相等的对象生成不同的哈希码，并且它与 equals() 的实现一致。

与往常一样，本文中显示的所有代码示例都可以在 GitHub 上找到


hashCode方法
hashCode()方法的作用是获取哈希码，返回的是一个int整数
@IntrinsicCandidate
public native int hashCode();
学过数据结构的都知道，哈希码的作用是确定对象在哈希表的索引下标。比如HashSet和HashMap就是使用了hashCode方法确定索引下标。如果两个对象返回的hashCode相同，
就被称为“哈希冲突”。

equals方法
equals()方法的作用很简单，就是判断两个对象是否相等，equals()方法是定义在Object类中，而所有的类的父类都是Object，所以如果不重写equals方法则会调用Object类
的equals方法。
public boolean equals(Object obj) {
   return (this == obj);
}
Object类的equals方法是用“==”号进行比较，在很多时候，因为==号比较的是两个对象的内存地址而不是实际的值，所以不是很符合业务要求。所以很多时候我们需要重写equals方
法，去比较对象中每一个成员变量的值是否相等。

问题来了
重写equals()方法就可以比较两个对象是否相等，为什么还要重写hashcode()方法呢？
因为HashSet、HashMap底层在添加元素时，会先判断对象的hashCode是否相等，如果hashCode相等才会用equals()方法比较是否相等。换句话说，HashSet和HashMap在判
断两个元素是否相等时，会先判断hashCode，如果两个对象的hashCode不同则必定不相等。

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
	Node<K, V>[] tab;
	Node<K, V> p;
	int n, i;
	if ((tab = table) == null || (n = tab.length) == 0)
		n = (tab = resize()).length;
	if ((p = tab[i = (n - 1) & hash]) == null)
		tab[i] = newNode(hash, key, value, null);
	else {
		Node<K, V> e;
		K k;
		if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))//先判断哈希码是否相等，再用equals判断是否相等
			e = p;
		else if (p instanceof TreeNode)
			e = ((TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value);
		else {
			for (int binCount = 0;; ++binCount) {
				if ((e = p.next) == null) {
					p.next = newNode(hash, key, value, null);
					if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
						treeifyBin(tab, hash);
					break;
				}
				if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
					break;
				p = e;
			}
		}
		if (e != null) { // existing mapping for key
			V oldValue = e.value;
			if (!onlyIfAbsent || oldValue == null)
				e.value = value;
			afterNodeAccess(e);
			return oldValue;
		}
	}
	++modCount;
	if (++size > threshold)
		resize();
	afterNodeInsertion(evict);
	return null;
}


下面我们做一个试验，有一个User类，只重写equals()方法，然后放到Set集合中去重。

public class User {

    private String id;

    private String name;

    private Integer age;
    
    public User(String id, String name, Integer age) {
        this.id = id;
        this.name = name;
        this.age = age;
    }
    
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        User user = (User) o;
        return Objects.equals(id, user.id) &&
            Objects.equals(name, user.name) &&
            Objects.equals(age, user.age);
    }
    
    //getter、setter、toString方法
}
然后我们循环创建10个成员变量的值都是一样的User对象，最后放到Set集合中去重。

public static void main(String[] args) {
    List<User> list = new ArrayList<>();
    for (int i = 0; i < 10; i++) {
        User user = new User("1", "张三", 18);
        list.add(user);
    }
    Set<User> set = new HashSet<>(list);
    for (User user : set) {
        System.out.println(user);
    }
    List<User> users = list.stream().distinct().collect(Collectors.toList());
    System.out.println(users);
}
按道理我们预期会去重，只剩下一个“张三”的user，但实际上因为没有重写hashCode方法，所以没有去重。



接着我们在User类里面重写一些hashCode方法再试试，其他不变。

public class User {
    //其他不变
    
    //重写hashCode方法
    @Override
    public int hashCode() {
        return Objects.hash(id, name, age);
    }
}
再运行，结果正确。

Set<User> set = new HashSet<>(list);将list加入set,其解释：
public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, java.io.Serializable{
	...
	public HashSet(Collection<? extends E> c) {
		map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
		addAll(c);
	}
	...
}

public abstract class AbstractCollection<E> implements Collection<E> {
	...
	public boolean addAll(Collection<? extends E> c) {
		boolean modified = false;
		for (E e : c)
			if (add(e))  //boolean java.util.Collection.add(E e)
				modified = true;
		return modified;
	}
	...
}

改写hashCode过程：Objects.hash(Object...values),即：
public final class Objects {
	...
	public static int hash(Object... values) {
		return Arrays.hashCode(values);
	}
	...
}

public class Arrays {
	...
	public static int hashCode(Object[] a) {
		if (a == null)
			return 0;
		int result = 1;
		for (Object element : a)
			result = 31 * result + (element == null ? 0 : element.hashCode());
		return result;
	}
	...
}


究其原因在于HashSet会先判断hashCode是否相等，如果hashCode不相等就直接认为两个对象不相等，不会再用equals()比较了。我们不妨看看重写hashCode方法和不重
写hashCode方法的哈希码。

这是不重写hashCode方法的情况，每个user对象的哈希码都不一样，所以HashSet会认为都不相等。



这是重写hashCode方法的情况，因为是用对象所有的成员变量的值计算出的哈希码，所以只要两个对象的成员变量都是相等的，则生成的哈希码是相同的。



那么有些人看到这里，就会问，如果两个对象返回的哈希码都是一样的话，是不是就一定相等？

答案是不一定的，因为HashSet、HashMap判断哈希码相等后还会再用equals()方法判断。

总而言之：

哈希码不相等，则两个对象一定不相同。
哈希码相等，两个对象不一定相同。
两个对象相同，则哈希码和值都一定相等。
总结
所以回到开头讲的那句，只要重写 equals，就必须重写 hashCode，这是一个很重要的细节，如果不注意的话，很容易发生业务上的错误。

特别是有时候我们明明用了HashSet，distinct()去重，但是就是不生效，这时应该回头看看重写了equals()和hashCode()方法了吗？
*/